//第一次尝试写，但是只适用于全是正数的情况
class Solution {
public:
    int subarraySum(vector<int>& nums, int k) {
        int left=0,right=0,sz=nums.size(),ans=0;
        vector<int> tmp(sz);
        tmp[0]=nums[0];
        if(sz==1&&nums[0]!=k)
        return 0;
        for(int i=1;i<sz;i++)
        {
            tmp[i]=tmp[i-1]+nums[i];
        }
        while(right<sz)
        {
            while(tmp[right]>k)
            {
                tmp[right]-=nums[left];
                if(left<sz-1)
                left++;
            }
            if(tmp[right]==k) ans++;
            right++;
        }
        return ans;
    }
};

//正解，采用哈希表和前缀和，求前缀和数组第i个位置前有多少个sum-i的数
ass Solution {
public:
    int subarraySum(vector<int>& nums, int k) {
        int ans=0;
    unordered_map<int,int>hash{{0,1}};
        int sum=0;
        for(auto& i:nums)
        {
            sum+=i;
            if(hash.count(sum-k)) ans+=hash[sum-k];
            hash[sum]++;
        }
        return ans;

    }
};
